/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sentence-similarity
   @Language: C++
   @Datetime: 19-04-28 17:01
   */

class Solution {
public:
	/**
	 * @param words1: a list of string
	 * @param words2: a list of string
	 * @param pairs: a list of string pairs
	 * @return: return a boolean, denote whether two sentences are similar or not
	 */
	bool isSentenceSimilarity(vector<string> &words1, vector<string> &words2, vector<vector<string> > &pairs) {
		// write your code here
		if(words1.size()!=words2.size()) return false;
		unordered_multimap<string,string> dict;
		for(const auto &p:pairs){
			dict.insert(make_pair(p[0],p[1]));
			dict.insert(make_pair(p[1],p[0]));
		}
		for(int i=0; i<words1.size(); ++i){
			bool found = words1[i]==words2[i];
			for(auto r=dict.equal_range(words1[i]); r.first!=r.second && !found; ++r.first)
				found |= r.first->second == words2[i];
			if(!found) return false;
		}
		return true;
	}
};
